package ljl.codetop300;

import java.util.Arrays;

/**
 * 人家说是归并排序，我上来就写了个堆排序，我透？
 *
 */
public class _912_sorts {

  static class heap_sort {
    public int[] sortArray(int[] nums) {
      heapSort(nums);
      return nums;
    }

    void heapSort(int[] nums) {
      makeHeap(nums);
      for (int i = nums.length - 1; i > 0; i--) {
        int t = nums[i];
        nums[i] = nums[0];
        nums[0] = t;
        downFiltration(nums, 0, i);
      }
    }
    void makeHeap(int[] nums) {
      for (int i = nums.length / 2; i >= 0 ; i--) {
        downFiltration(nums, i, nums.length);
      }
    }
    void downFiltration(int[] nums, int start, int endExcluded) {
      int e = nums[start];
      for (int j = 2 * start + 1; j < endExcluded; j = j * 2 +1) {
        if (j < endExcluded - 1 && nums[j + 1] > nums[j])
          j++;
        if (nums[j] <= e) {
          break;
        }
        nums[start] = nums[j];
        start = j;
      }
      nums[start] = e;
    }
  }

  /**
   * 官方和我思路是一样的，但是写法比我的笨一截子
   * 但是效率应该大差不差
   */
  static class off {
    class Solution {
      public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
      }

      public void heapSort(int[] nums) {
        int len = nums.length - 1;
        buildMaxHeap(nums, len);
        for (int i = len; i >= 1; --i) {
          swap(nums, i, 0);
          len -= 1;
          maxHeapify(nums, 0, len);
        }
      }

      public void buildMaxHeap(int[] nums, int len) {
        for (int i = len / 2; i >= 0; --i) {
          maxHeapify(nums, i, len);
        }
      }

      public void maxHeapify(int[] nums, int i, int len) {
        for (; (i << 1) + 1 <= len;) {
          int lson = (i << 1) + 1;
          int rson = (i << 1) + 2;
          int large;
          if (lson <= len && nums[lson] > nums[i]) {
            large = lson;
          } else {
            large = i;
          }
          if (rson <= len && nums[rson] > nums[large]) {
            large = rson;
          }
          if (large != i) {
            swap(nums, i, large);
            i = large;
          } else {
            break;
          }
        }
      }

      private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
      }
    }
  }

  /**
   * 一直分，分成一个之后开始合并，合并到 tmp 里
   * 理论上每次都需要一个新的 tmp，怎么复用？
   */
  static class merge_sort {

    public static void main(String[] args) {
      int[] res = new merge_sort().sortArray(new int[]{1, 5, 4, 3, 2, 1});
      System.out.println(Arrays.toString(res));
    }
    public int[] sortArray(int[] nums) {
      int[] res = new int[nums.length];
      mergeSort(nums, res, 0, nums.length - 1);
      return nums;
    }

    /**
     * 我期待的是 mergeSort 完，nums 是排序好的数据
     */
    void mergeSort(int[] nums, int[] tmp, int from, int to) {
      if (from >= to) return;
      int mid = (from + to) >>> 1;
      mergeSort(nums, tmp, from, mid);
      mergeSort(nums, tmp, mid + 1, to);
      int i = from;
      int j = mid + 1;
      int k = from;
      while (i <= mid && j <= to) {
        int v1 = nums[i];
        int v2 = nums[j];
        int min;
        if (v1 <= v2) {
          min = v1;
          i++;
        } else {
          min = v2;
          j++;
        }
        tmp[k++] = min;
      }
      while (i <= mid) tmp[k++] = nums[i++];
      while (j <= to) tmp[k++] = nums[j++];
      System.arraycopy(tmp, from, nums, from, to + 1 - from);
    }

  }
}
